/*
https://leetcode.cn/problems/maximum-number-of-groups-getting-fresh-donuts/solution/de-dao-xin-xian-tian-tian-quan-de-zui-du-pzra/
 */
import java.util.HashMap;
import java.util.Map;

public class Solution1815 {
    public int maxHappyGroups(int batchSize, int[] groups) {
        int[] nums=new int[batchSize];
        for (int group : groups) {
            nums[group%batchSize]++;
        }
        long start=0;
        for (int i=batchSize-1;i>=1;i--){
            start=(start<<5)|nums[i];
        }
        Map<Long,Integer> map=new HashMap<>();
        return dfs(map,batchSize,start)+nums[0];
    }

    private int dfs(Map<Long, Integer> map, int batchSize, long start) {
        if (start==0){
            return 0;
        }
        if (!map.containsKey(start)){
            long total=0;
            for (int i=1;i<batchSize;i++){
                long amount=((start>>(i-1)*5)&31);
                total+=i*amount;
            }
            int best=0;
            for (int i=1;i<batchSize;i++){
                long amount=((start>>(i-1)*5)&31);
                if (amount>0){
                    int result=dfs(map,batchSize,start-(1L<<(i-1)*5));
                    if ((total-i)%batchSize==0){
                        result++;
                    }
                    best=Math.max(best,result);
                }
            }
            map.put(start,best);
        }
        return map.get(start);
    }

    public static void main(String[] args) {
        System.out.println(new Solution1815().maxHappyGroups(3,new int[]{1,2,3,4,5,6}));
    }
}
